package com.github.kezhenxu94.playground.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. Longest Substring Without Repeating Characters
 *
 * Given a string, find the length of the longest substring without repeating
 * characters.
 *
 * Examples:
 *
 * Given "abcabcbb", the answer is "abc", which the length is 3.
 *
 * Given "bbbbb", the answer is "b", with the length of 1.
 *
 * Given "pwwkew", the answer is "wke", with the length of 3. Note that the
 * answer must be a substring, "pwke" is a subsequence and not a substring.
 *
 * @author ke.zhen.xu
 */
public class Solution003LongestSubstringWithoutRepeatingCharacters {

	public int lengthOfLongestSubstring (String s) {
		if (s.length () <= 1) {
			return s.length ();
		}
		Map<Character, Integer> map = new HashMap<> ();
		int                     max = 0;
		int                     idx = 0;
		for (int i = 0; i < s.length (); i++) {
			int     tmp;
			Integer orDefault = map.getOrDefault (s.charAt (i), 0);
			orDefault = idx > orDefault ? idx : orDefault;
			if ((tmp = i - orDefault + 1) > max) {
				max = tmp;
			}
			if (map.containsKey (s.charAt (i))) {
				idx = i;
			}
			map.put (s.charAt (i), i);
		}
		return max;
	}
}
